package BranchBound;

public class OptimalScheduling {
    private int tasks;        //任务数
    private int machines;        //机器数
    private int best;     //最优值
    private int[] taskTimes;      //每个任务所需的时间序列
    private int[] machineTimes;    //每台机器所需时间序列
    private int[] currentSolution;      //当前路径
    private int[] bestSolution;  //最优调度：bestSolution[i]=m表示把第i项任务分配给第m台机器

    public OptimalScheduling(int tasks, int machines, int[] taskTimes) {
        this.tasks = tasks;
        this.machines = machines;
        this.taskTimes = taskTimes;
        this.machineTimes = new int[machines];

        this.best = Integer.MAX_VALUE;
        this.bestSolution = new int[tasks];
        this.currentSolution = new int[tasks];
    }

    //回溯搜索
    public void backtrack(int dep) {
        //当到达最后一个任务的时候，进行判断
        if (dep == tasks) {
            int currentBest = getLongestTime();
            //best依次减小
            if (currentBest < best) {
                best = currentBest;
                //把当前solution复制到最佳分配方案
                System.arraycopy(currentSolution, 0, bestSolution, 0, tasks);
            }
            return;
        }

        //将当前遍历到的任务时间放入每一个机器
        for (int i = 0; i < machines; i++) {//遍历每一个机器
            machineTimes[i] += taskTimes[dep];//将遍历到的任务时间放入机器
            currentSolution[dep] = i + 1;//将当前路径的对应机器的位置记录下来
            //如果当前机器时间小于最大的时间
            if (machineTimes[i] < best) {
                backtrack(dep + 1);//搜索下一个任务
            }
            machineTimes[i] -= taskTimes[dep];//回溯一步
        }
    }

    //计算完成任务的最长时间
    public int getLongestTime() {
        int time = 0;
        for (int i = 0; i < machines; i++) {
            if (machineTimes[i] > time) {
                time = machineTimes[i];
            }
        }
        return time;
    }

    public int getBest() {
        return best;
    }

    public void setBest(int best) {
        this.best = best;
    }

    public int[] getBestSolution() {
        return bestSolution;
    }

    public void setBestSolution(int[] bestSolution) {
        this.bestSolution = bestSolution;
    }
}
